package 剑指offer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @description:
 * @author: ywk
 * @date: 2020-11-08
 */
public class 矩阵的最小路径和 {

    public static void main(String[] args) {
        int[][] matrix = {{1, 3, 5, 9}, {8, 1, 3, 4}, {5, 0, 6, 1}, {8, 8, 4, 0}};
        System.out.println(minPathSum2(matrix));

        //数组去重方法三
        String[] array = {"a","b","c","c","d","e","e","e","a"};
        List<String> list = new ArrayList<>();
        for(int i=0;i<array.length;i++){
            for(int j=i+1;j<array.length;j++){
                if(array[i] == array[j]){
                    j = ++i;
                }
            }
            list.add(array[i]);
        }
        String[] arrayResult = list.toArray(new String[list.size()]);
        System.out.println(Arrays.toString(arrayResult));
    }
    static int min = Integer.MAX_VALUE;

    /**
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public static int minPathSum(int[][] matrix) {
        // write code here
        return inPathVal(matrix, 0, 0, 0);
    }

    public static int inPathVal(int[][] matrix, int i, int j, int sum) {

        int path = matrix[i][j];
        sum = sum + path;
        if (i == matrix.length - 1 && j == matrix[0].length - 1) {
            if (sum < min) {
                min = sum;
            }
        }
        if (i + 1 < matrix.length) {
            inPathVal(matrix, i + 1, j, sum);


        }
        if (j + 1 < matrix[0].length) {
            inPathVal(matrix, i, j + 1, sum);
        }
        return min;
    }

    public static int minPathSum2 (int[][] matrix) {
        // write code here
        int m=matrix.length;
        if(m==0) return 0;
        int n=matrix[0].length;
        if(n==0) return 0;
        for(int i=1;i<m;i++) matrix[i][0]+=matrix[i-1][0];
        for(int j=1;j<n;j++) matrix[0][j]+=matrix[0][j-1];
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                matrix[i][j]+=Math.min(matrix[i][j-1],matrix[i-1][j]);
            }
        }
        return matrix[m-1][n-1];
    }
}
